//
//  归并排序.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/3/3.
//  归并排序
/*
 平均时间复杂度：O(nlogn)
 最佳时间复杂度：O(n)
 最差时间复杂度：O(nlogn)
 空间复杂度：O(n)
 排序方式：In-place
 稳定性：稳定
 */

import Foundation

/// 归并排序(递归法)
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func mergeSortRecursion(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }

    let mid = arr.count / 2
    let leftArr = mergeSortRecursion(Array(arr.prefix(mid)))
    let rightArr = mergeSortRecursion(Array(arr.suffix(from: mid)))
    
    /// 合并数组
    func merge(leftArr: [Int], rightArr: [Int]) -> [Int] {
        var merged = [Int]()
        var a = 0, b = 0
        while a < leftArr.count && b < rightArr.count  {
            if leftArr[a] <= rightArr[b] {
                merged.append(leftArr[a])
                a += 1
            } else {
                merged.append(rightArr[b])
                b += 1
            }
        }
        // 将剩余的数据添加到数组
        merged.append(contentsOf: leftArr.suffix(from: a))
        merged.append(contentsOf: rightArr.suffix(from: b))
        
        return merged
    }

    return merge(leftArr: leftArr, rightArr: rightArr)
}

/// 归并排序(迭代法)
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func mergeSortIterative(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    var a = arr
    
    /// 合并数组
    func merge(_ leftArr: [Int], _ rightArr: [Int]) -> [Int] {
        var merged = [Int]()
        var a = 0, b = 0
        while a < leftArr.count && b < rightArr.count  {
            if leftArr[a] <= rightArr[b] {
                merged.append(leftArr[a])
                a += 1
            } else {
                merged.append(rightArr[b])
                b += 1
            }
        }
        
        // 将剩余的数据添加到数组
        merged.append(contentsOf: leftArr.suffix(from: a))
        merged.append(contentsOf: rightArr.suffix(from: b))
        
        return merged
    }
    
    let n = arr.count
    /**
     * 迭代的方式是指底而上，递归是自顶向下
     * sz 是每次左右部分中元素的个数
     * 外层循环控制分组
     * 内层循环控制归并
     */
    var sz = 1
    while sz < n {
        var i = 0
        while i < n - sz {
            // 将l...r分成两段，终点为mid
            let l = i, mid = i + sz - 1, r = min(i + sz + sz - 1, n - 1)
            // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
            if a[mid] > a[mid + 1] {
                // 合并两个子数组
                let tempArr = merge(Array(a[l...mid]), Array(a[(mid + 1)...r]))
                a.replaceSubrange(l...r, with: tempArr)
            }
            i += sz + sz
        }
        sz *= 2
    }

    return a
}
